package my.jwds.p10;

public class IsMatch {

    public static void main(String[] args) {

        Solution obj = new Solution();
        long start = System.currentTimeMillis();

        System.out.println(obj.isMatch("aasdfasdfasdfasdfas",
                "aasdf.*asdf.*asdf.*asdf.*s"));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {

        public boolean isMatch(String s, String p) {
            int n = s.length(),m = p.length();
            boolean [][] dp = new boolean[m+1][n+1];
            dp[0][0] = true;


            for (int i = 1; i <= m; i++) {
                if (p.charAt(i-1) == '*'){
                    dp[i][0] = dp[i-2][0];
                }
            }

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (p.charAt(i-1) == '*'){

                        if (p.charAt(i-2) == '.' || p.charAt(i-2) == s.charAt(j-1)){
                            dp[i][j] = dp[i][j-1] || dp[i-2][j-1];
                        }

                        dp[i][j] = dp[i][j] || dp[i-2][j];


                    }else if ((p.charAt(i-1) == '.' || p.charAt(i-1) == s.charAt(j-1)) ){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }
            }
            return dp[m][n];
        }

    }
}